package com.erbao.datastructurearithmetic.tyro;

import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * @author CaoBaoYin
 * @since 21/8/4 11:04
 */
public class Class6 {

    public static void main(String[] args) {
        /*TreeNode root = new TreeNode('F');
        root.left = new TreeNode('C');
        root.right = new TreeNode('E');
        root.left.left = new TreeNode('A');
        root.left.right = new TreeNode('D');
        root.left.right.left = new TreeNode('B');
        root.right.left = new TreeNode('H');
        root.right.right = new TreeNode('G');
        root.right.right.left = new TreeNode('M');

        pre (root);
        System.out.println();
        in (root);
        System.out.println();
        post(root);*/


        int[] preOrder = {3,9,20,15,7};
        int[] inOrder = {9,3,15,20,7};
        buildTree(preOrder, inOrder);
    }

    /**
     * 前序
     */
    private static void pre(TreeNode<?> root) {
        if (root == null) {
            return;
        }

        System.out.print(root.val);
        pre(root.left);
        pre(root.right);
    }

    /**
     * 中序
     */
    private static void in(TreeNode<?> root) {
        if (root == null) {
            return;
        }

        in(root.left);
        System.out.print(root.val);
        in(root.right);
    }

    /**
     * 后序
     */
    private static void post(TreeNode<?> root) {
        if (root == null) {
            return;
        }

        post(root.left);
        post(root.right);
        System.out.print(root.val);
    }

    private static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        if (lists.length == 1) return lists[0];

        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(node -> node.val));
        for (ListNode listNodeHead : lists) {
            if (listNodeHead != null){
                priorityQueue.add(listNodeHead);
            }
        }

        if (priorityQueue.isEmpty()) return null;

        ListNode head = priorityQueue.poll();
        ListNode cursor = head;
        if (cursor.next != null) {
            priorityQueue.offer(cursor.next);
        }
        while (!priorityQueue.isEmpty()) {
            ListNode poll = priorityQueue.poll();
            if (poll.next != null) {
                priorityQueue.offer(poll.next);
            }
            cursor.next = poll;
            cursor = cursor.next;
        }

        return head;
    }

    private static class ListNode {
        int val;
        ListNode next;

        public ListNode() {
        }

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 判断完全一样的树
     */
    private static boolean isSameTree(TreeNode<?> p, TreeNode<?> q) {
        if (p == null ^ q == null) return false;

        if (p == null && q == null) return true;

        return p.val.equals(q.val) && isSameTree(p.left, q.left) && isSameTree(p.right, q.right) ;
    }

    /**
     * 判断对称二叉树
     */
    private static boolean isSymmetric(TreeNode<?> root) {
        if (root == null) return true;

        return isSymmetric(root.left, root.right);
    }

    /**
     * 判断对称二叉树
     * @param p 左
     * @param q 右
     */
    private static boolean isSymmetric(TreeNode<?> p, TreeNode<?> q) {
        if (p == null ^ q == null) return false;

        if (p == null && q == null) return true;

        return p.val.equals(q.val) && isSymmetric(p.left, q.right) && isSymmetric(p.right, q.left) ;
    }

    /**
     * 求树的最大深度
     */
    public static int maxDepth(TreeNode<?> root) {
        if (root == null) return 0;

        if (root.left==null && root.right == null) return 1;

        int maxLeft = maxDepth(root.left);
        int maxRight = maxDepth(root.right);
        return maxLeft > maxRight ? maxLeft+1 : maxRight+1;
    }

    /**
     * 构建二叉树
     * @param preorder 先序遍历数组
     * @param inorder 中序遍历数组
     * @return 二叉树根结点
     */
    private static TreeNode<Integer> buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null) return null;

        if (preorder.length != inorder.length) return null;

        int length = preorder.length;
        if (preorder.length == 1) return new TreeNode<>(preorder[0]);

        HashMap<Integer, Integer> inMap = new HashMap<>(length);
        for (int i = 0; i < length; i++) {
            inMap.put(inorder[i], i);
        }

        return buildTree(inMap, preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
    }

    private static TreeNode<Integer> buildTree(HashMap<Integer, Integer> inMap, int[] preorder, int l1, int r1, int[] inorder, int l2, int r2) {
        if (l1 > r1 || l2 > r2) {
            return null;
        }

        int rootValue = preorder[l1];
        TreeNode<Integer> root = new TreeNode<>(rootValue);

        int find = inMap.get(rootValue);
        root.left = buildTree(inMap, preorder, l1+1, l1-l2+find, inorder, l2,find-1);
        root.right = buildTree(inMap, preorder, l1-l2+find+1, r1, inorder, find+1, r2);
        return root;
    }


}
